package code.c03_stackQueue.application;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/3 12:21
 * @package code.c03_stackQueue.application
 * @description 【栈的综合运用】用栈解决迷宫问题
 */

import java.util.Stack;

/**
 * 用栈求解一条迷路路径类
 */
public class MazeClass {
    final int MAX_SIZE = 20;
    // 迷宫数组
    int[][] mg;
    // 迷宫行和列数
    int m, n;

    public MazeClass(int m, int n) {
        this.m = m;
        this.n = n;
        mg = new int[MAX_SIZE][MAX_SIZE];
    }

    public void setMg(int[][] a) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mg[i][j] = a[i][j];
            }
        }
    }

    /**
     * 求一条从（xi,yi） 到 （xe,ye）的迷宫路径
     *
     * @param xi
     * @param yi
     * @param xe
     * @param ye
     * @return
     */
    boolean mgPath(int xi, int yi, int xe, int ye) {
        int i, j, di, i1 = 0, j1 = 0;
        boolean find;
        Box box, e;
        Stack<Box> st = new Stack<>();
        st.push(new Box(xi, yi, -1));
        mg[xi][yi] = -1;
        while (!st.empty()) {
            box = st.peek();
            i = box.i;
            j = box.j;
            di = box.di;
            if (i == xe && j == ye) {
                int cnt = 1;
                while (!st.empty()) {
                    e = st.pop();
                    System.out.print(String.format("[%d,%d] ", e.i, e.j));
                    if (cnt % 5 == 0) {
                        System.out.println();
                    }
                    cnt++;
                }
                System.out.println();
                return true;
            }
            find = false;
            while (di < 3 && !find) {
                di++;
                switch (di) {
                    case 0:
                        i1 = i - 1;
                        j1 = j;
                        break;
                    case 1:
                        i1 = i;
                        j1 = j + 1;
                        break;
                    case 2:
                        i1 = i + 1;
                        j1 = j;
                        break;
                    case 3:
                        i1 = i;
                        j1 = j - 1;
                        break;
                }
                if (mg[i1][j1] == 0) {
                    find = true;
                }
            }
            if (find) {
                e = st.pop();
                e.di = di;
                st.push(e);
                st.push(new Box(i1, j1, -1));
                mg[i1][j1] = -1;
            } else {
                mg[i][j] = 0;
                st.pop();
            }
        }

        return false;
    }

    public static void main(String[] args) {
        MazeClass mazeClass = new MazeClass(6, 6);
        int[][] a = {
                {1, 1, 1, 1, 1, 1},
                {1, 0, 1, 0, 0, 1},
                {1, 0, 0, 1, 1, 1},
                {1, 0, 1, 0, 0, 1},
                {1, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1}
        };

        mazeClass.setMg(a);

        if (!mazeClass.mgPath(1,1,4,4)){
            System.out.println("不存在迷宫路径");
        }

    }
}

class Box {
    // 方块的行号
    int i;
    // 方块的列号
    int j;
    // 下一个可走相邻方位的方位号
    int di;

    public Box(int i, int j, int di) {
        this.i = i;
        this.j = j;
        this.di = di;
    }

}